#include<string>
#include<vector>
using namespace std;

class Solution {
private:
    int count = 0;
    string ans = "";
    vector<bool> flag;

    void dfs(int n, int k, string& cur) {
        if (cur.size() == n) {
            count++;
            if (count == k) ans = cur;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!flag[i]) {
                cur.push_back('0' + i);
                flag[i] = true;
                dfs(n, k, cur);
                flag[i] = false;
                cur.pop_back();
                if (!ans.empty()) return;  // 已找到目标排列，提前结束
            }
        }
    }

public:
    string getPermutation(int n, int k) {
        flag.assign(n + 1, false);
        string cur = "";
        dfs(n, k, cur);
        return ans;
    }
};